package demo.suanfa;

import java.util.*;

public class _贪心算法 {
    public static void main(String[] args) {
//        _孩子分饼干();
//        _分硬币();
//        _最多次数活动安排();
        _最短时间活动安排();
//        _股票最大收益();
    }

    private static void _股票最大收益() {
        /**
         * 已知一段时间内每天的股票价格 求最大收益
         * 输入
         * 2, 21, 6, 28, 56
         * 输出
         * 69
         * 说明
         * 0 19 19 41 76
         * 2买入21时卖出 收益19
         * 6买入28时卖出 收益19+22=41
         * 28买入56时卖出 收益41+28=69
         *
         */
        int[] nums = {2, 21, 6, 28, 56};
        int n = nums.length;
        // 2 21 28 6  56
        // 0 19 26 26 76

        //2 21 6  28 56
        //0 19 19 41 76
        // 求最大收益
        int max = 0;
        // 贪心算法 - 每次有利润就交易
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {// 如果今天价格比昨天高，就昨天买入今天卖出
                max += nums[i] - nums[i - 1];
            }
        }
        System.out.println(max);
    }

    private static void _最短时间活动安排() {
        // 配置时间start，结束时间end
        // 输出所有任务完成的最短时间
        int[][] tasks = {
                {1, 1},
                {2, 2},
                {3, 3},
        };
        /**
         * 思路：
         * 所有任务按结束时间倒序 优先执行时间长的
         * 配置时间累加
         * max=开始时间累加+最后一个任务完成时间
         *
         * config_sum+=start
         * max = max(max,config_sum+end)
         */
        // 结束时间降序
        Arrays.sort(tasks, (a, b) -> b[1] - a[1]);

        int config_sum = 0;
        int max = 0;
        for (int[] task : tasks) {
            config_sum += task[0];
            max = Math.max(max, config_sum + task[1]);
        }
        // 排序后顺序：{3,3}, {2,2}, {1,1}
        //机器1: configSum=3, 完成时间=3+3=6
        //机器2: configSum=3+2=5, 完成时间=5+2=7
        //机器3: configSum=5+1=6, 完成时间=6+1=7
        //最终完成时间 = max(6,7,7) = 7
        System.out.println(max);
    }


    private static void _最多次数活动安排() {
        // 在一系列有重叠的活动中，选择最多的互不冲突的活动
        // 固定输入：二维数组，每行表示一个活动 [开始时间, 结束时间]
        // 输入最多可以安排活动次数
        int[][] activities = {
                {1, 4},
                {3, 5},
                {0, 6},
                {5, 7},
                {3, 9},
                {5, 9},
                {6, 10},
                {8, 11},
                {8, 12},
                {2, 14},
                {12, 16}
        };

        List<Activity> list = new ArrayList<>();
        for (int i = 0; i < activities.length; i++) {
            list.add(new Activity(i, activities[i][0], activities[i][1]));
        }

        // 按结束时间升序
        Collections.sort(list, Comparator.comparingInt(a -> a.end));
        List<Activity> selected = new ArrayList<>();
        selected.add(list.get(0)); // 添加第一个
        int lastTime = selected.get(0).end;
        for (int i = 1; i < list.size(); i++) {
            Activity activity = list.get(i);
            if (activity.start > lastTime) {
                selected.add(activity);
                lastTime = activity.end;
            }
        }
        System.out.println("索引\t开始时间\t结束时间");
        for (Activity activity : selected) {
            System.out.println(activity.idx + "\t" + activity.start + "\t" + activity.end);
        }
    }

    static class Activity {
        int idx;
        int start;
        int end;

        public Activity(int idx, int start, int end) {
            this.idx = idx;
            this.start = start;
            this.end = end;
        }

        public int getIdx() {
            return idx;
        }

        public void setIdx(int idx) {
            this.idx = idx;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }
    }

    private static void _最多次数活动安排2() {
        // 在一系列有重叠的活动中，选择最多的互不冲突的活动
        // 固定输入：二维数组，每行表示一个活动 [开始时间, 结束时间]
        // 输入最多可以安排活动次数
        int[][] activities = {
                {1, 4},
                {3, 5},
                {0, 6},
                {5, 7},
                {3, 9},
                {5, 9},
                {6, 10},
                {8, 11},
                {8, 12},
                {2, 14},
                {12, 16}
        };
        int[][] tasks = new int[activities.length][activities[0].length + 1];
        for (int i = 0; i < activities.length; i++) {
            tasks[i][0] = activities[i][0];
            tasks[i][1] = activities[i][1];
            tasks[i][2] = i;// 补充索引位，输出用
        }

        // 按结束时间升序 结束时间短在前面
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        List<int[]> selected = new ArrayList<>();
        selected.add(tasks[0]); // 添加第一个
        int lastTime = selected.get(0)[1];
        for (int i = 1; i < tasks.length; i++) {
            int[] task = tasks[i];
            if (task[0] > lastTime) {
                selected.add(task);
                lastTime = task[1];
            }
        }
        System.out.println("索引\t开始时间\t结束时间");
        for (int[] activity : selected) {
            System.out.println(activity[2] + "\t" + activity[0] + "\t" + activity[1]);
        }
    }


    private static void _分硬币() {
        /*
         * 给定金额，输出金额 67 的找零方案：
         *   25元硬币: 2枚
         *   10元硬币: 1枚
         *   5元硬币: 1枚
         *   1元硬币: 2枚
         * 总硬币数量: 6
         *
         * 金额 7 无法找零
         *
         * 金额 186 的找零方案：
         *   100元硬币: 1枚
         *   50元硬币: 1枚
         *   20元硬币: 1枚
         *   10元硬币: 1枚
         *   5元硬币: 1枚
         *   1元硬币: 1枚
         * 总硬币数量: 6
         *
         * 金额 0 的找零方案：
         * 总硬币数量: 0
         */
        int[] coins = {1, 5, 10, 20, 50, 100};
        int tar = 67;
        Arrays.sort(coins);

        Map<Integer, Integer> map = new HashMap<>();
        int remain = tar;
        // 倒叙 从大到小
        for (int i = coins.length - 1; i >= 0; i--) {
            int coin = coins[i];
            if (remain >= coin) {
                int count = remain / coin;
                map.put(coin, count);
                remain -= coin * count;
                System.out.println("需要:" + coin + "元," + count + "个,剩余:" + remain);
            }

            if (remain == 0) {
                break;
            }
        }
    }

    private static void _孩子分饼干() {
        /**
         * 有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃最多一个饼干，且
         * 只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。
         * 输入输出样例：
         * 输入：12
         * 输入：123
         * 输出：2
         */
        // 孩子饥饿度
        int[] g = {2, 6, 7, 8};
        // 饼干大小
        int[] s = {1, 2, 3, 4};

        Arrays.sort(g);
        Arrays.sort(s);

        int childrenIdx = 0;
        int cookieIdx = 0;
        int count = 0;

        while (childrenIdx < g.length && cookieIdx < s.length) {
            if (s[cookieIdx] >= g[childrenIdx]) {
                count++;// 这个孩子吃饱了
                childrenIdx++; // 考虑下一个孩子
            }
            cookieIdx++; // 无论是否满足，都要考虑下一个饼干
        }
        System.out.println(count);
    }

}
